#include "memory.h"
#include "lib.h"
#include "printk.h"

st_global_mem_desc g_mem_mgmt = {{0}, 0};

int g_zone_dma_index = 0;   
int g_zone_normal_index = 0;    // low 1GB RAM, was mapped in pagetable
int g_zone_unmapped_index = 0;  // above 1GB RAM, unmapped in pagetable

unsigned long *g_global_cr3 = NULL;

// 定义16类slab内存池以适配不同大小
st_slab_cache g_kmalloc_cache_size[16] = {
    {32, 0, 0, NULL, NULL, NULL, NULL},
    {64, 0, 0, NULL, NULL, NULL, NULL},
    {128, 0, 0, NULL, NULL, NULL, NULL},
    {256, 0, 0, NULL, NULL, NULL, NULL},
    {512, 0, 0, NULL, NULL, NULL, NULL},
    {1024, 0, 0, NULL, NULL, NULL, NULL},
    {2048, 0, 0, NULL, NULL, NULL, NULL},
    {4096, 0, 0, NULL, NULL, NULL, NULL},
    {8192, 0, 0, NULL, NULL, NULL, NULL},
    {16384, 0, 0, NULL, NULL, NULL, NULL},
    {32768, 0, 0, NULL, NULL, NULL, NULL},
    {65536, 0, 0, NULL, NULL, NULL, NULL},
    {131072, 0, 0, NULL, NULL, NULL, NULL},
    {262144, 0, 0, NULL, NULL, NULL, NULL},
    {524288, 0, 0, NULL, NULL, NULL, NULL},
    {1048576, 0, 0, NULL, NULL, NULL, NULL},
};

unsigned long page_init(st_page *page, unsigned long flags) {
    page->attr |= flags;

    if (!page->ref_cnt || (page->attr & PG_SHARED)) {
        page->ref_cnt++;
        page->zone_struct->total_pages_link++;
    } 

    return 1;
}

unsigned long page_clean(st_page *page) {
    page->ref_cnt--;
    page->zone_struct->total_pages_link--;
    if (!page->ref_cnt) {
        page->attr &= PG_PTABLE_MAPPED;
    }
    return 1;
}

unsigned long get_page_attribute(st_page *page) {
    if (page == NULL) {
        color_printk(RED, BLACK, "get_page_attribute() error: page == NULL\n");
        return 0;
    } else {
        return page->attr;
    }
}

unsigned long set_page_attribute(st_page *page, unsigned long flags) {
    if (page == NULL) {
        color_printk(RED, BLACK, "set_page_attribute() error: page == NULL\n");
        return 0;
    } else {
        page->attr = flags;
        return 1;
    }
}

void memory_init() {
    int i, j;
    unsigned long total_mem = 0;
    st_mem_E820 *p = NULL;
    unsigned long start, end;

    color_printk(BLUE, BLACK, "Display physics address map, type(1:RAM, 2:ROM or reserved, 3:ACPI Reclaim memory, 4:ACPI NVS memory, Others:Undefined)\n");
    p = (st_mem_E820 *)0xffff800000007e00;

    for (i = 0; i < 32; ++i) {
        if (p->type == 1)
            color_printk(ORANGE, BLACK, "Address:%#018lx\tLength:%#018lx\tType:%#010x\n", p->address, p->length, p->type);
        if (p->type == 1) {
            total_mem += p->length;
        }

        g_mem_mgmt.e820[i].address = p->address;
        g_mem_mgmt.e820[i].length = p->length;
        g_mem_mgmt.e820[i].type = p->type;
        g_mem_mgmt.e820_len = i;

        p++;
        if (p->type > 4 || p->length == 0 || p->type < 1) {
            break;
        }
    }
    color_printk(ORANGE, BLACK, "OS can used total RAM:%#018lx\n", total_mem);

    // 按2M进行分页，地址要进行对齐，前后修剪掉不足2M的部分
    total_mem = 0;
    for (i = 0; i <= g_mem_mgmt.e820_len; ++i) {
        if (g_mem_mgmt.e820[i].type != 1) {
            continue;
        }
        start = PAGE_2M_ALIGN(g_mem_mgmt.e820[i].address);
        end = (g_mem_mgmt.e820[i].address + g_mem_mgmt.e820[i].length) & PAGE_2M_MASK;  // end不能向上取整，只能向下取整
        if (end <= start) {
            continue;
        }
        total_mem += (end - start) >> PAGE_2M_SHIFT;
    }
    color_printk(ORANGE, BLACK, "OS can used total 2M pages:%#010x=%010d\n", total_mem, total_mem);

    // 获取最大的物理地址，目前最大地址记录在最后一条有效物理内存段信息中，其中不仅包含可用物理内存，还包括内存空洞和ROM地址空间
    total_mem = g_mem_mgmt.e820[g_mem_mgmt.e820_len].address + g_mem_mgmt.e820[g_mem_mgmt.e820_len].length;

    // 位图位于内核程序结束地址的下一个页，这里按4k对齐
    g_mem_mgmt.bits_map = (unsigned long *)((g_mem_mgmt.end_brk + PAGE_4K_SIZE - 1) & PAGE_4K_MASK);
    g_mem_mgmt.bits_size = total_mem >> PAGE_2M_SHIFT;
    g_mem_mgmt.bits_len = (((unsigned long)(total_mem >> PAGE_2M_SHIFT) + sizeof(long) * 8 - 1) / 8) & (~(sizeof(long) - 1));
    memset(g_mem_mgmt.bits_map, 0xff, g_mem_mgmt.bits_len);

    // 构造pages，pages数组存放在bits_map后一个页
    g_mem_mgmt.pages_struct = (st_page *)(((unsigned long)g_mem_mgmt.bits_map + g_mem_mgmt.bits_len + PAGE_4K_SIZE - 1) & PAGE_4K_MASK);
    g_mem_mgmt.pages_size = total_mem >> PAGE_2M_SHIFT;
    g_mem_mgmt.pages_len = ((total_mem >> PAGE_2M_SHIFT) * sizeof(st_page) + sizeof(long) - 1) & (~(sizeof(long) - 1));
    memset(g_mem_mgmt.pages_struct, 0x00, g_mem_mgmt.pages_len);

    // 构造zones，zones数组存放在pages后一页
    g_mem_mgmt.zones_struct = (st_zone *)(((unsigned long)g_mem_mgmt.pages_struct + g_mem_mgmt.pages_len + PAGE_4K_SIZE - 1) & PAGE_4K_MASK);
    g_mem_mgmt.zones_size = 0;
    g_mem_mgmt.zones_len = (5 * sizeof(st_zone) + sizeof(long) - 1) & (~(sizeof(long) - 1));
    memset(g_mem_mgmt.zones_struct, 0x00, g_mem_mgmt.zones_len);

    for (i = 0; i <= g_mem_mgmt.e820_len; ++i) {
        st_zone *z;
        st_page *p;
        unsigned long *b;

        if (g_mem_mgmt.e820[i].type != 1) {
            continue;
        }
        start = PAGE_2M_ALIGN(g_mem_mgmt.e820[i].address);
        end = (g_mem_mgmt.e820[i].address + g_mem_mgmt.e820[i].length) & PAGE_2M_MASK;  // end不能向上取整，只能向下取整
        if (end <= start) {
            continue;
        }

        // zone init
        z = g_mem_mgmt.zones_struct + g_mem_mgmt.zones_size;
        g_mem_mgmt.zones_size++;
        z->zone_start_addr = start;
        z->zone_end_addr = end;
        z->zone_len = end - start;
        z->page_using_cnt = 0;
        z->page_free_cnt = z->zone_len >> PAGE_2M_SHIFT;
        z->total_pages_link = 0;
        z->attr = 0;
        z->gmd_struct = &g_mem_mgmt;
        z->pages_len = z->page_free_cnt;
        z->pages_group = (st_page *)(g_mem_mgmt.pages_struct + (start >> PAGE_2M_SHIFT));

        // page init
        p = z->pages_group;
        for (j = 0; j < z->pages_len; ++j, ++p) {
            p->zone_struct = z;
            p->phy_addr = start + PAGE_2M_SIZE * j;
            p->attr = 0;
            p->ref_cnt = 0;
            p->age = 0;
            *(g_mem_mgmt.bits_map + ((p->phy_addr >> PAGE_2M_SHIFT) >> 6)) ^= 1Ul << ((p->phy_addr >> PAGE_2M_SHIFT) & 63);
        }
    }
    
    // 0~2MB内存中可用空间不足一页，前面初始化跳过了，其中包含多个物理内存段，还有内核程序，所以必须特殊初始化
    g_mem_mgmt.pages_struct->zone_struct = g_mem_mgmt.zones_struct;
    g_mem_mgmt.pages_struct->phy_addr = 0;
    set_page_attribute(g_mem_mgmt.pages_struct, PG_PTABLE_MAPPED | PG_KERNEL_INIT | PG_KERNEL);
    g_mem_mgmt.pages_struct->ref_cnt = 1;
    g_mem_mgmt.pages_struct->age = 0;

    g_mem_mgmt.zones_len = (g_mem_mgmt.zones_size * sizeof(st_zone) + sizeof(long) - 1) & (~(sizeof(long) - 1));
    color_printk(ORANGE, BLACK, "bits_map:%#018lx, bits_size:%#018lx, bits_length:%#018lx\n", g_mem_mgmt.bits_map, g_mem_mgmt.bits_size, g_mem_mgmt.bits_len);
    color_printk(ORANGE, BLACK, "pages_struct:%#018lx, pages_size:%#018lx, pages_length:%#018lx\n", g_mem_mgmt.pages_struct, g_mem_mgmt.pages_size, g_mem_mgmt.pages_len);
    color_printk(ORANGE, BLACK, "zones_struct:%#018lx, zones_size:%#018lx, zones_length:%#018lx\n", g_mem_mgmt.zones_struct, g_mem_mgmt.zones_size, g_mem_mgmt.zones_len);

    g_zone_dma_index = 0;
    g_zone_normal_index = 0;
    g_zone_unmapped_index = 0;

    for (i = 0; i < g_mem_mgmt.zones_size; ++i) {
        st_zone *z = g_mem_mgmt.zones_struct + i;
        color_printk(ORANGE, BLACK, "zone start_addr:%#018lx, zone end_addr:%#018lx, zone len:%#018lx, pages_group:%#018lx, pages len:%#018lx\n", z->zone_start_addr, z->zone_end_addr, z->zone_len, z->pages_group, z->pages_len);
        if (z->zone_start_addr >= 0x100000000 && !g_zone_unmapped_index) {
            g_zone_unmapped_index = i;
        }
    }

    color_printk(ORANGE, BLACK, "g_zone_dma_index:%d\tg_zone_normal_index:%d\tg_zone_unmapped_index:%d\n", g_zone_dma_index, g_zone_normal_index, g_zone_unmapped_index);

    g_mem_mgmt.end_of_struct = (unsigned long)((unsigned long)g_mem_mgmt.zones_struct + g_mem_mgmt.zones_len + sizeof(long) * 32) & (~(sizeof(long) - 1));
    color_printk(ORANGE, BLACK, "start_code:%#018lx, end_code:%#018lx, end_data:%#018lx, end_brk:%#018lx, end_of_struct:%#018lx\n", g_mem_mgmt.start_code, g_mem_mgmt.end_code, g_mem_mgmt.end_data, g_mem_mgmt.end_brk, g_mem_mgmt.end_of_struct);

    i = Virt_To_Phy(g_mem_mgmt.end_of_struct) >> PAGE_2M_SHIFT;
    for (j = 1; j <= i; ++j) {
        st_page *tmp_page = g_mem_mgmt.pages_struct + j;
        page_init(tmp_page, PG_PTABLE_MAPPED | PG_KERNEL_INIT | PG_KERNEL);
        SET_PAGE_BITSMAP(tmp_page);
        tmp_page->zone_struct->page_using_cnt++;
        tmp_page->zone_struct->page_free_cnt--;
    }

    g_global_cr3 = get_gdt();
    color_printk(INDIGO, BLACK, "g_global_cr3\t:%#018lx\n", g_global_cr3);
    color_printk(INDIGO, BLACK, "*g_global_cr3\t:%#018lx\n", *Phy_To_Virt(g_global_cr3) & (~0xff));
    color_printk(PURPLE, BLACK, "**g_global_cr3\t:%#018lx\n", *Phy_To_Virt(*Phy_To_Virt(g_global_cr3) & (~0xff)) & (~0xff));

    color_printk(ORANGE, BLACK, "1.g_mem_mgmt.bits_map:%#018lx\tzone_struct->page_using_cnt:%d\tzone_struct->page_free_cnt:%d\n", g_mem_mgmt.bits_map[0], g_mem_mgmt.zones_struct->page_using_cnt, g_mem_mgmt.zones_struct->page_free_cnt);

    // 清除线性地址0处的映射，此后内核程序只存在于线性地址0xffff800000000000处
    for (i = 0; i < 10; ++i) {
        *(Phy_To_Virt(g_global_cr3) + i) = 0UL;
    }
    FLUSH_TLB();
}

inline unsigned long *get_gdt() {
    unsigned long *tmp;
    __asm__ __volatile__ (
        "movq %%cr3, %0 \n\t"
        :"=r"(tmp)
        :
        :"memory"
    );
    return tmp;
}

st_page *alloc_pages(int zone_select, int number, unsigned long page_flags) {
    int i;
    unsigned long page = 0;
    unsigned long attr = 0;
    int zone_start = 0;
    int zone_end = 0;

    if (number >= 64 || number < 0) {
        color_printk(RED, BLACK, "alloc_pages() error: number is invalid\n");
        return NULL;
    }

    switch (zone_select)
    {
    case ZONE_DMA:
        zone_start = 0;
        zone_end = g_zone_dma_index;
        attr = PG_PTABLE_MAPPED;
        break;
    case ZONE_NORMAL:
        zone_start = g_zone_dma_index;
        zone_end = g_zone_normal_index;
        attr = PG_PTABLE_MAPPED;
        break;
    case ZONE_UNMAPPED:
        zone_start = g_zone_unmapped_index;
        zone_end = g_mem_mgmt.zones_size - 1;
        attr = 0;
        break;
    default:
        color_printk(RED, BLACK, "alloc_pages() error: zone_select index is invalid\n");
        return NULL;
    }

    for (i = zone_start; i <= zone_end; ++i) {
        st_zone *z;
        unsigned long j;
        unsigned long start, end;
        unsigned long tmp;

        if ((g_mem_mgmt.zones_struct + i)->page_free_cnt < number) {
            continue;
        }
        
        z = g_mem_mgmt.zones_struct + i;
        start = z->zone_start_addr >> PAGE_2M_SHIFT;
        end = z->zone_end_addr >> PAGE_2M_SHIFT;

        tmp = 64 - start % 64;
        for (j = start; j <= end; j += j % 64 ? tmp : 64) {
            unsigned long *p = g_mem_mgmt.bits_map + (j >> 6);
            unsigned long shift = j % 64;
            unsigned long k = 0;
            unsigned long num = (1UL << number) - 1;

            for (k = shift; k < 64; ++k) {
                // 最多申请连续的63个页，位图不一定按unsigned long对齐，因此需要判断连续两个unsigned long的值
                if (!((k ? ((*p >> k) | (*(p + 1) << (64 - k))) : *p) & (num))) {
                    unsigned long l;
                    page = j + k - shift;
                    for (l = 0; l < number; ++l) {
                        st_page *pageptr = g_mem_mgmt.pages_struct + page + l;
                        SET_PAGE_BITSMAP(pageptr);
                        z->page_using_cnt++;
                        z->page_free_cnt--;
                        pageptr->attr = attr;
                    }
                    goto find_free_pages;
                }
            }
        }
    }

    color_printk(RED, BLACK, "alloc_pages() error: no page can alloc\n");

    return NULL;

find_free_pages:
    return (st_page *)(g_mem_mgmt.pages_struct + page);
}

st_slab_cache *slab_create(unsigned long size, void *(* constructor)(void *vir_addr, unsigned long arg), void *(* destructor)(void *vir_addr, unsigned long arg), unsigned long arg) {
    st_slab_cache *slab_cache = NULL;
    slab_cache = (st_slab_cache *)kmalloc(sizeof(st_slab_cache), 0);
    if (slab_cache == NULL) {
        color_printk(RED, BLACK, "slab_create()->kmalloc()=>slab_cache == NULL\n");
        return NULL;
    }
    memset(slab_cache, 0, sizeof(st_slab_cache));
    slab_cache->size = SIZEOF_LONG_ALIGN(size);
    slab_cache->total_using = 0;
    slab_cache->total_free = 0;

    slab_cache->cache_pool = (st_slab *)kmalloc(sizeof(st_slab), 0);
    if (slab_cache->cache_pool == NULL) {
        color_printk(RED, BLACK, "slab_create()->kmalloc()=>slab_cache->cache_pool == NULL\n");
        kfree(slab_cache);
        return NULL;
    }
    memset(slab_cache->cache_pool, 0, sizeof(st_slab));

    slab_cache->cache_dma_pool = NULL;
    slab_cache->constructor = constructor;
    slab_cache->destructor = destructor;
    list_init(&slab_cache->cache_pool->list);

    slab_cache->cache_pool->page = alloc_pages(ZONE_NORMAL, 1, 0);
    if (slab_cache->cache_pool->page == NULL) {
        color_printk(RED, BLACK, "slab_create()->kmalloc()=>slab_cache->cache_pool->page == NULL\n");
        kfree(slab_cache->cache_pool);
        kfree(slab_cache);
        return NULL;
    }
    page_init(slab_cache->cache_pool->page, PG_KERNEL);
    slab_cache->cache_pool->using_cnt = 0;
    slab_cache->cache_pool->free_cnt = PAGE_2M_SIZE / slab_cache->size;
    slab_cache->total_free = slab_cache->cache_pool->free_cnt;
    slab_cache->cache_pool->vir_addr = Phy_To_Virt(slab_cache->cache_pool->page->phy_addr);

    slab_cache->cache_pool->color_cnt = slab_cache->cache_pool->free_cnt;
    slab_cache->cache_pool->color_len = ((slab_cache->cache_pool->color_cnt + sizeof(unsigned long) * 8 - 1) >> 6) << 3;
    slab_cache->cache_pool->color_map = (unsigned long *)kmalloc(slab_cache->cache_pool->color_len, 0);
    if (slab_cache->cache_pool->color_map == NULL) {
        color_printk(RED, BLACK, "slab_create()->kmalloc()=>slab_cache->cache_pool->color_map == NULL\n");
        kfree(slab_cache->cache_pool);
        kfree(slab_cache);
        return NULL;
    }
    memset(slab_cache->cache_pool->color_map, 0, slab_cache->cache_pool->color_len);
    return slab_cache;
}

unsigned long slab_destroy(st_slab_cache *slab_cache) {
    st_slab *slab_p = slab_cache->cache_pool;
    st_slab *tmp_slab = NULL;
    if (slab_cache->total_using != 0) {
        color_printk(RED, BLACK, "slab_cache->total_using != 0\n");
        return 0;
    }

    while (! list_is_empty(&slab_p->list)) {
        tmp_slab = slab_p;
        slab_p = container_of(list_next(&slab_p->list), st_slab, list);
        list_del(&tmp_slab->list);
        kfree(tmp_slab->color_map);
        page_clean(tmp_slab->page);
        free_pages(tmp_slab->page, 1);
        kfree(tmp_slab);
    }
    kfree(slab_p->color_map);
    page_clean(slab_p->page);
    free_pages(slab_p->page, 1);
    kfree(slab_p);
    kfree(slab_cache);
    return 1;
}

void *slab_malloc(st_slab_cache *slab_cache, unsigned long arg) {
    st_slab *slab_p = slab_cache->cache_pool;
    st_slab *tmp_slab = NULL;
    int j = 0;

    if (slab_cache->total_free == 0) {  // 内存池扩容
        tmp_slab = (st_slab *)kmalloc(sizeof(st_slab), 0);
        if (tmp_slab == NULL) {
            color_printk(RED, BLACK, "slab_malloc()->kmalloc()=>tmp_slab == NULL\n");
            return NULL;
        }
        memset(tmp_slab, 0, sizeof(st_slab));
        list_init(&tmp_slab->list);
        tmp_slab->page = alloc_pages(ZONE_NORMAL, 1, 0);
        if (tmp_slab->page == NULL) {
            color_printk(RED, BLACK, "slab_malloc()->kmalloc()=>tmp_slab->page == NULL\n");
            kfree(tmp_slab);
            return NULL;
        }
        page_init(tmp_slab->page, PG_KERNEL);
        tmp_slab->using_cnt = 0;
        tmp_slab->free_cnt = PAGE_2M_SIZE / slab_cache->size;
        tmp_slab->vir_addr = Phy_To_Virt(tmp_slab->page->phy_addr);
        tmp_slab->color_cnt = tmp_slab->free_cnt;
        tmp_slab->color_len = ((tmp_slab->color_cnt + sizeof(unsigned long) * 8 - 1) >> 6) << 3;
        tmp_slab->color_map = (unsigned long *)kmalloc(tmp_slab->color_len, 0);
        if (tmp_slab->color_map == NULL) {
            color_printk(RED, BLACK, "slab_malloc()->kmalloc()=>tmp_slab->color_map == NULL\n");
            free_pages(tmp_slab->page, 1);
            kfree(tmp_slab);
            return NULL;
        }
        memset(tmp_slab->color_map, 0, tmp_slab->color_len);
        list_add_to_behind(&slab_cache->cache_pool->list, &tmp_slab->list);
        slab_cache->total_free += tmp_slab->free_cnt;

        for (j = 0; j < tmp_slab->color_cnt; ++j) {
            if ((*(tmp_slab->color_map + (j >> 6)) & (1UL << (j % 64))) == 0) {
                *(tmp_slab->color_map + (j >> 6)) |= 1UL << (j % 64);
                tmp_slab->using_cnt++;
                tmp_slab->free_cnt--;
                slab_cache->total_using++;
                slab_cache->total_free--;
                if (slab_cache->constructor != NULL) {
                    return slab_cache->constructor((char *)tmp_slab->vir_addr + slab_cache->size * j, arg);
                } else {
                    return (void *)((char *)tmp_slab->vir_addr + slab_cache->size * j);
                }
            }
        }
    } else {
        do {
            if (slab_p->free_cnt == 0) {
                slab_p = container_of(list_next(&slab_p->list), st_slab, list);
                continue;
            }

            for (j = 0; j < slab_p->color_cnt; ++j) {
                if (*(slab_p->color_map + (j >> 6)) == 0xffffffffffffffffUL) {  // 一次性判断64个
                    j += 63;    // 这里加63，for循环再加1，刚好64
                    continue;
                }
                if ((*(slab_p->color_map + (j >> 6)) & (1UL << (j % 64))) == 0) {
                    *(slab_p->color_map + (j >> 6)) |= 1UL << (j % 64);
                    slab_p->using_cnt++;
                    slab_p->free_cnt--;
                    slab_cache->total_using++;
                    slab_cache->total_free--;
                    if (slab_cache->constructor != NULL) {
                        return slab_cache->constructor((char *)slab_p->vir_addr + slab_cache->size * j, arg);
                    } else {
                        return (void *)((char *)slab_p->vir_addr + slab_cache->size * j);
                    }
                }
            }
        } while (slab_p != slab_cache->cache_pool);
    }

    color_printk(RED, BLACK, "slab_malloc() error: can't alloc\n");
    if (tmp_slab != NULL) {
        list_del(&tmp_slab->list);
        kfree(tmp_slab->color_map);
        page_clean(tmp_slab->page);
        free_pages(tmp_slab->page, 1);
        kfree(tmp_slab);
    }
    return NULL;
}

unsigned long slab_free(st_slab_cache *slab_cache, void *addr, unsigned long arg) {
    st_slab *slab_p = slab_cache->cache_pool;
    int index = 0;

    do {
        if (slab_p->vir_addr <= addr && addr <= slab_p->vir_addr + PAGE_2M_SIZE) {
            index = (addr - slab_p->vir_addr) / slab_cache->size;
            *(slab_p->color_map + (index >> 6)) ^= 1UL << (index % 64);
            slab_p->free_cnt++;
            slab_p->using_cnt--;
            slab_cache->total_free++;
            slab_cache->total_using--;
            if (slab_cache->destructor) {
                slab_cache->destructor(addr, arg);
            }

            if (slab_p->using_cnt == 0 && (slab_cache->total_free >= slab_p->color_cnt * 3 / 2)) {  // 有富余，内存池缩容
                list_del(&slab_p->list);
                slab_cache->total_free -= slab_p->color_cnt;
                kfree(slab_p->color_map);
                page_clean(slab_p->page);
                free_pages(slab_p->page, 1);
                kfree(slab_p);
            }
            return 1;
        } else {
            slab_p = container_of(list_next(&slab_p->list), st_slab, list);
            continue;
        }
    } while (slab_p != slab_cache->cache_pool);
    color_printk(RED, BLACK, "slab_free() error: address not in slab\n");

    return 0;
}

unsigned long slab_init() {
    st_page *page = NULL;
    unsigned long *virtual = NULL;
    unsigned long i, j;
    unsigned long tmp_addr = g_mem_mgmt.end_of_struct;

    for (i = 0; i < 16; ++i) {
        g_kmalloc_cache_size[i].cache_pool = (st_slab *)g_mem_mgmt.end_of_struct;
        g_mem_mgmt.end_of_struct = g_mem_mgmt.end_of_struct + sizeof(st_slab) + sizeof(long) * 10;
        list_init(&g_kmalloc_cache_size[i].cache_pool->list);
        g_kmalloc_cache_size[i].cache_pool->using_cnt = 0;
        g_kmalloc_cache_size[i].cache_pool->free_cnt = PAGE_2M_SIZE / g_kmalloc_cache_size[i].size;
        g_kmalloc_cache_size[i].cache_pool->color_cnt = g_kmalloc_cache_size[i].cache_pool->free_cnt;
        g_kmalloc_cache_size[i].cache_pool->color_len = ((g_kmalloc_cache_size[i].cache_pool->color_cnt + sizeof(unsigned long) * 8 - 1) >> 6) << 3;
        g_kmalloc_cache_size[i].cache_pool->color_map = (unsigned long *)g_mem_mgmt.end_of_struct;
        g_mem_mgmt.end_of_struct = (unsigned long)(g_mem_mgmt.end_of_struct + g_kmalloc_cache_size[i].cache_pool->color_len + sizeof(long) * 10) & (~(sizeof(long) - 1));
        memset(g_kmalloc_cache_size[i].cache_pool->color_map, 0xff, g_kmalloc_cache_size[i].cache_pool->color_len);

        for (j = 0; j < g_kmalloc_cache_size[i].cache_pool->color_cnt; ++j) {
            *(g_kmalloc_cache_size[i].cache_pool->color_map + (j >> 6)) ^= 1UL << (j % 64);
        }
        g_kmalloc_cache_size[i].total_free = g_kmalloc_cache_size[i].cache_pool->free_cnt;
        g_kmalloc_cache_size[i].total_using = 0;
    }

    // 标记slab内存池数组占用的内存页被使用
    i = Virt_To_Phy(g_mem_mgmt.end_of_struct) >> PAGE_2M_SHIFT;
    for (j = PAGE_2M_ALIGN(Virt_To_Phy(tmp_addr)) >> PAGE_2M_SHIFT; j <= i; ++j) {
        page = g_mem_mgmt.pages_struct + j;
        SET_PAGE_BITSMAP(page);
        page->zone_struct->page_using_cnt++;
        page->zone_struct->page_free_cnt--;
        page_init(page, PG_PTABLE_MAPPED | PG_KERNEL_INIT | PG_KERNEL);
    }

    color_printk(ORANGE, BLACK, "2.g_mem_mgmt.bits_map:%#018lx\tzone_struct->page_using_cnt:%d\tzone_struct->page_free_cnt:%d\n", *g_mem_mgmt.bits_map, g_mem_mgmt.zones_struct->page_using_cnt, g_mem_mgmt.zones_struct->page_free_cnt);
    // 为内存池的内存对象分配内存页
    for (i = 0; i < 16; ++i) {
        virtual = (unsigned long *)((g_mem_mgmt.end_of_struct + PAGE_2M_SIZE * i + PAGE_2M_SIZE - 1) & PAGE_2M_MASK);
        page = Virt_To_2M_Page(virtual);
        SET_PAGE_BITSMAP(page);
        page->zone_struct->page_using_cnt++;
        page->zone_struct->page_free_cnt--;
        page_init(page, PG_PTABLE_MAPPED | PG_KERNEL_INIT | PG_KERNEL);
        g_kmalloc_cache_size[i].cache_pool->page = page;
        g_kmalloc_cache_size[i].cache_pool->vir_addr = virtual;
    }

    color_printk(ORANGE, BLACK, "3.g_mem_mgmt.bits_map:%#018lx\tzone_struct->page_using_cnt:%d\tzone_struct->page_free_cnt:%d\n", *g_mem_mgmt.bits_map, g_mem_mgmt.zones_struct->page_using_cnt, g_mem_mgmt.zones_struct->page_free_cnt);
    color_printk(ORANGE, BLACK, "start_code:%#018lx, end_code:%#018lx, end_data:%#018lx, end_brk:%#018lx, end_of_struct:%#018lx\n", g_mem_mgmt.start_code, g_mem_mgmt.end_code, g_mem_mgmt.end_data, g_mem_mgmt.end_of_struct);
    return 1;
}

void free_pages(st_page *page, int number) {
    int i = 0;

    if (page == NULL) {
        color_printk(RED, BLACK, "free_pages() error: page is invalid\n");
        return;
    }

    if (number >= 64 || number <= 0) {
        color_printk(RED, BLACK, "free_pages() error: number is invalid\n");
        return;
    }

    for (i = 0; i < number; ++i) {
        CLEAR_PAGE_BITSMAP(page);       // 内页页对应bit位置0
        page->zone_struct->page_using_cnt--;
        page->zone_struct->page_free_cnt++;
        page->attr = 0;
    }
}

void *kmalloc(unsigned long size, unsigned long gfp_flags) {
    int i, j;
    st_slab *slab = NULL;
    
    if (size > 1048576) {       // 超过1MB
        color_printk(RED, BLACK, "kmalloc() error: kmalloc size too long:%08d\n", size);
        return NULL;
    }
    for (i = 0; i < 16; ++i) {  // 找出刚好满足大小的slab内存池
        if (g_kmalloc_cache_size[i].size >= size) {
            break;
        }
    }
    slab = g_kmalloc_cache_size[i].cache_pool;

    if (g_kmalloc_cache_size[i].total_free != 0) {  // 如果内存池还有空闲内存，找到对应slab对象
        do {
            if (slab->free_cnt == 0) {
                slab = container_of(list_next(&slab->list), st_slab, list);
            } else {
                break;
            }
        } while (slab != g_kmalloc_cache_size[i].cache_pool);
    } else {    // 内存池没有空闲内存，先对内存池扩容
        slab = kmalloc_create(g_kmalloc_cache_size[i].size);
        if (slab == NULL) {
            color_printk(BLUE, BLACK, "kmalloc()->kmalloc_create()=>slab == NULL\n");
            return NULL;
        }
        g_kmalloc_cache_size[i].total_free += slab->color_cnt;
        color_printk(BLUE, BLACK, "kmalloc()->kmalloc_create()<=size:%#010x\n", g_kmalloc_cache_size[i].size);
        list_add_to_before(&g_kmalloc_cache_size[i].cache_pool->list, &slab->list);
    }

    for (j = 0; j < slab->color_cnt; ++j) {
        if (*(slab->color_map + (j >> 6)) == 0xffffffffffffffffUL) {
            j += 63;
            continue;
        }

        if ((*(slab->color_map + (j >> 6)) & (1UL << (j % 64))) == 0) {
            *(slab->color_map + (j >> 6)) |= 1UL << (j % 64);
            slab->using_cnt++;
            slab->free_cnt--;
            g_kmalloc_cache_size[i].total_free--;
            g_kmalloc_cache_size[i].total_using++;
            return (void *)((char *)slab->vir_addr + g_kmalloc_cache_size[i].size * j);
        }
    }

    color_printk(BLUE, BLACK, "kmalloc() error: no memory can alloc\n");
    return NULL;
}

// 根据指定大小创建一个slab对象用于扩充内存池
st_slab *kmalloc_create(unsigned long size) {
    int i;
    st_slab *slab = NULL;
    st_page *page = NULL;
    unsigned long *vir_addr = NULL;
    long structsize = 0;

    page = alloc_pages(ZONE_NORMAL, 1, 0);
    if (page == NULL) {
        color_printk(RED, BLACK, "kmalloc_create()->alloc_pages()=>page == NULL\n");
        return NULL;
    }

    page_init(page, PG_KERNEL);

    switch (size) {
    case 32:
    case 64:
    case 128:
    case 256:
    case 512:
        vir_addr = Phy_To_Virt(page->phy_addr);
        structsize = sizeof(st_slab) + PAGE_2M_SIZE / size / 8;                  // 由于color_map比较大，页面末尾存放slab对象和slab对象的color_map
        slab = (st_slab *)((unsigned char *)vir_addr + PAGE_2M_SIZE - structsize);
        slab->color_map = (unsigned long *)((unsigned char *)slab + sizeof(st_slab));

        slab->free_cnt = (PAGE_2M_SIZE - (PAGE_2M_SIZE / size / 8) - sizeof(st_slab)) / size;
        slab->using_cnt = 0;
        slab->color_cnt = slab->free_cnt;
        slab->vir_addr = vir_addr;
        slab->page = page;
        list_init(&slab->list);

        slab->color_len = ((slab->color_cnt + sizeof(unsigned long) * 8 - 1) >> 6) << 3;
        memset(slab->color_map, 0xff, slab->color_len);

        for (i = 0; i < slab->color_cnt; ++i) {
            *(slab->color_map + (i >> 6)) ^= 1UL << (i % 64);
        }
        break;
    case 1024:
    case 2048:
    case 4096:
    case 8192:
    case 16384:
    case 32768:
    case 65536:
    case 131072:
    case 262144:
    case 524288:
    case 1048576:       // color_map比较小，通过kmalloc申请内存存放
        slab = (st_slab *)kmalloc(sizeof(st_slab), 0);
        
        slab->free_cnt = PAGE_2M_SIZE / size;
        slab->using_cnt = 0;
        slab->color_cnt = slab->free_cnt;
        slab->color_len = ((slab->color_cnt + sizeof(unsigned long) * 8 - 1) >> 6) << 3;
        slab->color_map = (unsigned long *)kmalloc(slab->color_len, 0);
        memset(slab->color_map, 0xff, slab->color_len);
        slab->vir_addr = Phy_To_Virt(page->phy_addr);
        slab->page = page;
        list_init(&slab->list);
        for (i = 0; i < slab->color_cnt; ++i) {
            *(slab->color_map + (i >> 6)) ^= 1UL << (i % 64);
        }
        break;
    default:
        color_printk(RED, BLACK, "kmalloc_create() error: wrong size:%08d\n", size);
        free_pages(page, 1);
        return NULL;
    }

    return slab;
}

unsigned long kfree(void *addr) {
    int i;
    int index;
    st_slab *slab = NULL;
    void *page_base_addr = (void *)((unsigned long)addr & PAGE_2M_MASK);

    for (i = 0; i < 16; ++i) {
        slab = g_kmalloc_cache_size[i].cache_pool;
        do {
            if (slab->vir_addr == page_base_addr) {
                index = (addr - slab->vir_addr) / g_kmalloc_cache_size[i].size;
                *(slab->color_map + (index >> 6)) ^= 1UL << (index % 64);
                slab->free_cnt++;
                slab->using_cnt--;
                g_kmalloc_cache_size[i].total_free++;
                g_kmalloc_cache_size[i].total_using--;

                // 考虑释放slab对象
                if ((slab->using_cnt == 0) && (g_kmalloc_cache_size[i].total_free >= slab->color_cnt * 3 / 2) && (g_kmalloc_cache_size[i].cache_pool != slab)) {
                    switch(g_kmalloc_cache_size[i].size) {
                        case 32:
                        case 64:
                        case 128:
                        case 256:
                        case 512:
                            list_del(&slab->list);
                            g_kmalloc_cache_size[i].total_free -= slab->color_cnt;
                            page_clean(slab->page);
                            free_pages(slab->page, 1);
                            break;
                        default:
                            list_del(&slab->list);
                            g_kmalloc_cache_size[i].total_free -= slab->color_cnt;
                            kfree(slab->color_map);
                            page_clean(slab->page);
                            free_pages(slab->page, 1);
                            kfree(slab);
                            break;
                    }
                }
                return 1;
            } else {
                slab = container_of(list_next(&slab->list), st_slab, list);
            }
        } while (slab != g_kmalloc_cache_size[i].cache_pool);
    }

    color_printk(RED, BLACK, "kfree() error: can't free memory\n");
    return 0;
}

void pagetable_init() {
    unsigned long i, j;
    unsigned long *tmp = NULL;

    g_global_cr3 = get_gdt();
    tmp = (unsigned long *)(((unsigned long)Phy_To_Virt((unsigned long)g_global_cr3 & (~0xfffUL))) + 8 * 256);
    // color_printk(YELLOW, BLACK, "1:%#018lx, %#018lx\t\t\n", (unsigned long)tmp, *tmp);
    tmp = Phy_To_Virt(*tmp & (~0xfffUL));
    // color_printk(YELLOW, BLACK, "2:%#018lx, %#018lx\t\t\n", (unsigned long)tmp, *tmp);
    tmp = Phy_To_Virt(*tmp & (~0xfffUL));
    // color_printk(YELLOW, BLACK, "3:%#018lx, %#018lx\t\t\n", (unsigned long)tmp, *tmp);

    for (i = 0; i < g_mem_mgmt.zones_size; ++i) {
        st_zone *z = g_mem_mgmt.zones_struct + i;
        st_page *p = z->pages_group;
        if (g_zone_unmapped_index && i == g_zone_unmapped_index) {
            break;
        }

        for (j = 0; j < z->pages_len; ++j, ++p) {
            tmp = (unsigned long *)(((unsigned long)Phy_To_Virt((unsigned long)g_global_cr3 & (~ 0xfffUL))) + (((unsigned long)Phy_To_Virt(p->phy_addr) >> PAGE_GDT_SHIFT) & 0x1ff) * 8);
            if (*tmp == 0) {    // 如果值为0表示未进行次级页表映射，申请一个4KB的内存作为次级页表
                unsigned long *virtual = kmalloc(PAGE_4K_SIZE, 0);  // GDT表仍然按4k分页
                SET_MPL4T(tmp, MK_MPL4T(Virt_To_Phy(virtual), PAGE_KERNEL_GDT));    // 次级页表的基地址写入当前表项
            }
            tmp = (unsigned long *)(((unsigned long)Phy_To_Virt((unsigned long)*tmp & (~ 0xfffUL))) + (((unsigned long)Phy_To_Virt(p->phy_addr) >> PAGE_1G_SHIFT) & 0x1ff) * 8);
            if (*tmp == 0) {    // 同上
                unsigned long *virtual = kmalloc(PAGE_4K_SIZE, 0);
                SET_PDPT(tmp, MK_PDPT(Virt_To_Phy(virtual), PAGE_KERNEL_DIR));
            }
            tmp = (unsigned long *)(((unsigned long)Phy_To_Virt((unsigned long)*tmp & (~ 0xfffUL))) + (((unsigned long)Phy_To_Virt(p->phy_addr) >> PAGE_2M_SHIFT) & 0x1ff) * 8);
            SET_PDT(tmp, MK_PDT(p->phy_addr, PAGE_KERNEL_PAGE));    // 这里采用三级页表，因此没有次级页表

            // if (j % 50 == 0) {
            //     color_printk(GREEN, BLACK, "@:%#018lx, %#018lx\t\n", (unsigned long)tmp, *tmp);
            // }
        }
    }
    FLUSH_TLB();
}